package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         56,
		Discription: "合并区间",
		Level:       2,
		Labels: map[string]int{
			"排序": 1,
		},
	})
}

func Merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] < intervals[j][0] {
			return true
		}

		if intervals[i][0] == intervals[j][0] && intervals[i][1] <= intervals[j][1] {
			return true
		}

		return false
	})

	res := [][]int{intervals[0]}
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] > res[len(res)-1][1] {
			//如果当前的区间的start大于总体区间的end，表示无交集，直接append
			res = append(res, intervals[i])
		} else {
			//当前区间的start在总体区间的end之前，但肯定在总体区间的start之后（排序）,右区间取最大
			res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])
		}
	}

	return res
}
